package routePlanner.algorithm;

import routePlanner.entities.Atraction;
import routePlanner.entities.AtractionType;
import routePlanner.entities.City;
import routePlanner.entities.CityConnection;
import routePlanner.entities.Vehicle;

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class DifferentDijkstra {

	/**
	 * Reprezentuje dystans do danej krawędzi. Używane do przechowywania w
	 * kolejce priorytetowej do wyboru najkrótszej krawędzi.
	 */
	class DistanceToEdge implements Comparable<DistanceToEdge> {
		// krawędź
		private final City edge;
		//odległość do tej krawędzi
		private long distance;

		public DistanceToEdge(City edge, long distance) {
			this.edge = edge;
			this.distance = distance;
		}

		public long getDistance() {
			return distance;
		}

		public void setDistance(long distance) {
			this.distance = distance;
		}

		public City getEdge() {
			return edge;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			DistanceToEdge other = (DistanceToEdge) obj;
			if (!getOuterType().equals(other.getOuterType()))
				return false;
			if (distance != other.distance)
				return false;
			if (edge != other.edge)
				return false;
			return true;
		}

		@Override
		public int compareTo(DistanceToEdge param) {
			int cmp = new Long(distance).compareTo(param.getDistance());

			if (cmp == 0) {
				return new Integer(edge.getId()).compareTo(param.getEdge().getId());
			}
			return 0;
		}

		private DifferentDijkstra getOuterType() {
			return DifferentDijkstra.this;
		}
	}

	//przechowuje krawędź, z której jest najbliżej do bieżącej określonej indeksem tablicy
	private CityConnection[] edgeTo;
	//przechowuje najkrótsze znalezione odległości do danego wierzchołka
	private Long[] distanceTo;
	//kolejka przechowująca bieżące krawędzie uszeregowane od najkrótszej do najdłuższej
	private Queue<DistanceToEdge> priorityQueue;

	public DifferentDijkstra(DirectedGraph graph, City source, Atraction atraction, boolean isAltitudeImportant) {
		//inicjacja wewnętrznych struktur
		edgeTo = new CityConnection[graph.getNumberOfVertices()];
		distanceTo = new Long[graph.getNumberOfVertices()];
		priorityQueue = new PriorityQueue<DistanceToEdge>(graph.getNumberOfVertices());

		//dla każdego wierzchołka v ustawiamy największa możliwą wartość jaką może przechowywać
		for (int v = 0; v < graph.getNumberOfVertices(); v++) {
			distanceTo[v] = Long.MAX_VALUE;
		}
		//odległość do wierzchołka źrodłowego to 0
		distanceTo[source.getId()] = 0L;

		//wstawiamy wierzhołek źrodłowy do kolejki, od niego rozpoczynamy poszukiwania
		priorityQueue.offer(new DistanceToEdge(source, 0L));

		//przeprowadzamy relaksację grafu, dopóki kolejka nie jest pusta
		while (!priorityQueue.isEmpty()) {
			relax(graph, priorityQueue.poll().getEdge(), atraction, isAltitudeImportant);
		}
	}

	private void relax(DirectedGraph graph, City v, Atraction atraction, boolean isAltitudeImportant) {
		//przeglądamy listy sąsiedztwa wszystkich wierzchołków
		for (CityConnection edge : graph.getNeighborhoodList(v.getId()-1)) {
			City next = edge.getEndCity();
			int w = next.getId() - 1;
			//na początek jako minimalną odległość przyjmujemy odległość zwykłą między miastami
			long minDistance = edge.getDistance();
			//warunek na położenie n.p.m. (jeśli jest istotne w procesie decyzyjnym, to jego wartość dodajemy do ścieżki)
			long weight = 0;
			if (isAltitudeImportant)
			{
				weight = next.getAltitude();
			}
			//warunek na występowanie wybranej atrakcji w mieście (jeśli jest, to dzielimy przez połowę)
			double decision = 1;
			if (next.getAtraction() == atraction)
			{
				decision = next.getAtraction().getRank();
			}
			//wyznaczenie ścieżki z wagami
			double distanceToChoose = (minDistance + weight)/decision;
			//sprawdzamy czy zmiana wierzchołka skróci dystans z wierzchołka źrodłowego
			if (distanceTo[w] > distanceToChoose) {
				distanceTo[w] = (long)distanceToChoose;
				edgeTo[w] = edge;
				DistanceToEdge dte = new DistanceToEdge(next, distanceTo[w]);
				//jeśli jest już krawędż o tej wadze, to ją usuwamy, bo znaleźliśmy lepszą drogę
				priorityQueue.remove(dte);
				//wstawiamy nową krawędź z aktualną znalezioną odleglością
				priorityQueue.offer(dte);
			}
		}
	}

	//metody do wyświetlenia drogi
	//jeśli zwrócona wartość wynosi Long.MAX_VALUE to oznacza, że dany wierzchołek jest nieosiągalny ze źródła
	public long getDistanceTo(City v) {
		return distanceTo[v.getId()-1];
	}

	//sprawdza, czy istnieje droga do danego wierzchołka
	public boolean hasPathTo(City v) {
		return distanceTo[v.getId()-1] < Long.MAX_VALUE;
	}

	public List<CityConnection> getPath(City start, City end) {
       List<CityConnection> path = new ArrayList<CityConnection>();
       //jeśli nie istnieje ścieżka lub jesteś już w tym mieście, zwróć pustą drogę
       if (start.getId() == end.getId() || !hasPathTo(end))
           return path;
       for (CityConnection e = edgeTo[end.getId()-1]; e.getStartCity().getId() != start.getId(); e = edgeTo[e.getStartCity().getId()-1]) {
           //dopóki istnieje krawędź, dodawaj ją do listy 
           path.add(e);
       }
       Collections.reverse(path);
       return path;
   }
}